//题目:
// 给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。
// 注意 这个数列必须是 严格 递增的。

// 示例 1:
// 输入: [1,3,5,4,7]
// 输出: 2
// 解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

// 示例 2:
// 输入: [2,2,2,2,2]
// 输出: 5
// 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
#include<iostream>
#include<limits.h>
#include<vector>

using namespace std;
//代码
class Solution 
{
public:
    int findNumberOfLIS(vector<int>& nums) 
    {
        //1.创建dp表————dp[i].first表示以nums[i]为结尾的最长递增子序列的长度;dp[i].second表示以nums[i]为结尾的最长递增子序列出现的次数
        vector<pair<int,int>> dp(nums.size(),make_pair(1,1));
        //2.初始化
        //3.填表
        int max_len=1;
        for(int i=1;i<nums.size();i++)
        {
            for(int j=i-1;j>=0;j--)
                if(nums[i]>nums[j] && 1+dp[j].first>=dp[i].first)
                {
                    //说明此前dp[i].first不是最大长度
                    if(1+dp[j].first>dp[i].first)
                        dp[i].second=dp[j].second,dp[i].first=1+dp[j].first;
                    else if(1+dp[j].first==dp[i].first)
                        dp[i].second+=dp[j].second; 
                }
        }
        //4.确定返回值
        int ret=0,max_val=INT_MIN;
        for(int i=0;i<nums.size();i++)
        {
            if(dp[i].first>max_val) 
                ret=dp[i].second,max_val=dp[i].first;
            else if(dp[i].first==max_val)
                ret+=dp[i].second;
        }
        return ret;
    }
};